package ljl.alg.wangzheng_camp.round1.sort;

import java.util.*;

public class _56_merge_interval {
    
    /**
     * 1 2 3 4 5 6 7 8 9
     * 1   3
     *   2   4
     *     33
     * */
    public int[][] merge3(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        Arrays.sort(intervals, Comparator.comparingInt(i -> i[0]));
        int[] prev = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            if (prev[1] < intervals[i][0]) {
                res.add(prev);
                prev = intervals[i];
            } else {
                prev[1] = Math.max(prev[1], intervals[i][1]);
            }
        }
        res.add(prev);
        return res.toArray(new int[0][]);
    }
    
    /**
     * 我的解法又笨逼了？
     *
     * 优化完更慢了？
     *
     * */
    public int[][] merge(int[][] intervals) {
        LinkedList<int[]> res = new LinkedList<>();
        Arrays.sort(intervals, Comparator.comparingInt(i -> i[0]));
        for (int[] interval : intervals) {
            if (res.size() == 0 || res.peekLast()[1] < interval[0]) {
                res.offer(interval);
            } else {
                res.peekLast()[1] = Math.max(res.peekLast()[1], interval[1]);
            }
        }
        return res.toArray(new int[0][]);
    }
    
}
